Java中元素的大小比較

? ? equals-Object 類：默認(rèn)比較兩個(gè)對(duì)象地址是否相等
? ? Comparable接口： return > 0 標(biāo)志當(dāng)前對(duì)象 > 0

Return = 0 表示當(dāng)前對(duì)象= 0

Return < 0 表示當(dāng)前對(duì)象< 0

? ? Comparator:接口(更靈活)：對(duì)原來Student類無影響 可以實(shí)現(xiàn)無數(shù)種比較———策略模式

return =0 ?o1 =o2

Return > 0 o1 >o2;

Return < 0 o1 <o2

Java.lang.Comparable:一個(gè)類實(shí)現(xiàn)了這個(gè)接口，就說明該類具備了可比較的能力

Public int compareTo(Object o):當(dāng)前對(duì)象和傳入對(duì)象o比較（死板）

Java.lang.Comparator：比較器。Student類無需事先此接口，專門的比較Student的類大小關(guān)系實(shí)現(xiàn)此皆苦，這種類稱為比較器

Public int compare(Object o1,Object o2):比較o1和o2的大小

AgeSec

AgeDesc
優(yōu)先級(jí)隊(duì)列&TopK

? ? PriorityQueue優(yōu)先級(jí)隊(duì)列(基于堆)：滿足隊(duì)列的三大操作：

入隊(duì)offer：調(diào)用堆的add方法

出隊(duì)poll：按照優(yōu)先級(jí)出隊(duì)，最高先出調(diào)用堆的extractMax()

查看隊(duì)首元素peek：查看堆頂元素

操作系統(tǒng)的作業(yè)調(diào)度（JDK的PriorityQueue基于最小堆實(shí)現(xiàn),需要調(diào)整為最大堆（原o1-o2改為o2-o1）2）

? ? TopK問題：取大構(gòu)建小堆 取小構(gòu)建大堆

時(shí)間復(fù)雜度 O（nlogk）

? ? ? ?空間復(fù)雜度 O（k）

兩種解決思路：1.排序法Nlogn 2.優(yōu)先級(jí)隊(duì)列 nlogk 3.最優(yōu)解 ：快排partition思想O（n）
Map和BST

二叉樹：理論基礎(chǔ)

二分搜索樹——TreeMap(紅黑樹，二分搜索樹)

哈希表——HashSet,HashMap

? ? Map和Set:

set存儲(chǔ)不重復(fù)的線性表——若只是判斷元素是否存在，或者過濾重復(fù)元素，使用Set集合

Map:存儲(chǔ)的數(shù)據(jù)是一種映射關(guān)系：需要根據(jù)不重復(fù)的key對(duì)應(yīng)value，需要使用Map集合

**，Map和Set是一種專門用來進(jìn)行搜索的容器或者數(shù)據(jù)結(jié)構(gòu)，其搜索德效率 與具體的實(shí)例化子類有關(guān)。****

盡量不要使用Map和Set集合進(jìn)行遍歷，對(duì)于這倆集合的遍歷操作是效率比較低的操作。使用Set和Map集合的核心操作在于搜索

? ? Map集合的常用操作：

? ? Map集合內(nèi)部的元素之間的先后順序與插入順序關(guān)系不大（put(key,value）
? ? 根據(jù)Key 取得value: get(key) getOrDefault（key,dafaultValue）
? ? Map集合中刪除元素 ：remove(key)
? ? Map集合的遍歷：（不到萬不得已，不要使用）：collection 接口及其子類可以很方便的使用for_each循環(huán)進(jìn)行遍歷，但是Map和Collection幾個(gè)沒有任何關(guān)系：keySet(); values();entrySet()【Set<map.Entry<K,V>> entrySet()】
? ? Map集合的搜索 contains方法在Map中是非常高效的

（HashMap中接近O(1)）TreeMap中接近O（logN）

? ? Set集合的使用，等同于List,都是Collection的子接口 最常用Set集合的場(chǎng)景，（元素去重）

***Map 存映射 Set存不重復(fù)元素，用于去重***

? ? 二分搜索樹（BST）

? ? 核心操作在于查找 3 {1.是個(gè)二叉樹；2,。所有節(jié)點(diǎn)值滿足：根節(jié)點(diǎn) }左子樹的所有節(jié)點(diǎn)，根節(jié)點(diǎn)<右子樹的所有節(jié)點(diǎn)，此處不考慮等于的情況（JDK中的BST沒有重復(fù)元素3；存儲(chǔ)的元素必須具備可比較性，Comparable或者傳入Comparator）
? ? 規(guī)律：{1,；中序遍歷得到的結(jié)果就是一個(gè)升序集合 2.源于最小最大值 最小值：第一個(gè)node.left==null 最大值：第一個(gè)node.right == null；3.在BST中插入一個(gè)新元素,這個(gè)元素一定是葉子結(jié)點(diǎn)位置插入！}）